#include<iostream>
#include<vector>
#include<string>
#include<unordered_set>
using namespace std;

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int len = nums.size();
        vector<int> dp(len, 0);
        int ans = 0;
        for (int i = 2; i < len; i++) {
            if (nums[i] + nums[i - 2] == 2 * nums[i - 1]) {
                dp[i]++;
                i++;
                while (i < len && nums[i] + nums[i - 2] == 2 * nums[i - 1]) {
                    ans += dp[i - 1];
                    dp[i] += dp[i - 1] + 1;
                    i++;
                }
                ans += dp[i - 1];
                i--;
            }
        }
        return ans;
    }
};

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int len = arr.size();
        if (len < 3) {
            if (len == 1)
                return 1;
            else if (arr[0] == arr[1])
                return 1;
            else
                return 2;
        }
        vector<int> dp(len, 0);
        int maxn = 0;
        int flag = 1;
        for (int i = 2; i < len; i++) {
            if ((arr[i - 1] > arr[i] && arr[i - 1] > arr[i - 2]) ||
                (arr[i - 1] < arr[i] && arr[i - 1] < arr[i - 2])) {
                dp[i] += 3;
                i++;
                while (i < len &&
                    ((arr[i - 1] > arr[i] && arr[i - 1] > arr[i - 2]) ||
                        (arr[i - 1] < arr[i] && arr[i - 1] < arr[i - 2]))) {
                    // maxn = max(dp[i - 1], maxn);
                    dp[i] += dp[i - 1] + 1;
                    i++;
                }
                maxn = max(dp[i - 1], maxn);
            }
            else if (flag && (arr[i - 1] != arr[i] || arr[i - 1] != arr[i - 2])) {
                maxn = max(maxn, 2);
                flag = 0;
            }
        }
        return maxn == 0 ? 1 : maxn;
    }
};

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        s = '-' + s;
        int len = s.size();
        unordered_set<string> hash;
        for (auto& s : wordDict) {
            hash.insert(s);
        }
        vector<bool> dp(len, false);
        dp[0] = true;
        int j = 1;
        for (int i = 1; i < len; i++) {
            for (int j = 1; j <= i; j++) {
                if (dp[j - 1] && hash.count(s.substr(j, i - j + 1))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len - 1];
    }
};

class Solution {
public:

    int arr[26];

    int findSubstringInWraproundString(string s) {
        int len = s.size();
        vector<int> dp(len, 1);
        int ans = 0;
        for (int i = 1; i < len; i++) {
            if ((s[i - 1] - 'a' + 1) % 26 + 'a' == s[i]) {
                dp[i] += dp[i - 1];
            }
        }
        for (int i = 0; i < len; i++) {
            if (arr[s[i] - 'a'] < dp[i]) {
                arr[s[i] - 'a'] = dp[i];
            }
        }
        for (auto& e : arr) {
            ans += e;
        }
        return ans;
    }
};

